The present invention relates to the art of data compression. It finds particular application in conjunction with a hardware implementation of high speed data compression for medical diagnostic images that will be described with particular reference thereto. It is to be appreciated, however, that the invention will also find application in conjunction with the compression of other types of image and non-image data either in hardware or software implementation.
Heretofore, various techniques have been developed for reducing the volume of data for more efficient storage and for faster transfer rates in bandwidth limited systems. Run length coding is one of the most commonly used data compression techniques. However, its coding and pattern matching algorithms have a very restricted application, such as half tone images and text compression. Although ideally suited for facsimile transmissions, run length coding is not a particularly suited to medical diagnostic images which have a wide range of gray scale.
Pattern matching is another common data compression technique. In pattern matching, the data is examined for frequently repeating words or data groups. This technique is particularly applicable to text data where a limited number of words tend to repeat frequently. However, the technique is of limited application in image data where the data tends not to have such a high repetition rate.
The data compression techniques that are better suited to image data commonly require two passes. In the first pass, the magnitude of the data is reduced by eliminating redundancy. The magnitude reduction can be achieved by various techniques such as linear predictive coding (LPC), discreet cosine transforms (DCT), and dictionary building. The first pass is relatively straightforward and generally amenable to synchronous pipeline operation.
The second pass, which packs the data, is less amenable to fast processing. Common packing techniques include Huffman coding, arithmetic coding, and field packing. In Huffman coding, the unique bit pattern of variable length is allocated to each input value, with common values having smaller patterns. In the arithmetic coding, each value is represented by an interval in an arbitrary precision binary fraction. In field packing, several values of a packing factor field are packed into each word. Although Hoffman coding is typically performed synchronous to the output bit stream, it is limited by the bit rate. Arithmetic coding is performed in software and is not generally considered amenable to hardware implementations. Field packing is typically implemented by pre-scanning incoming data to determine which packing factor to use before performing the actual packing. The pre-scan can be done in parallel, but at a considerable expense in hardware resources and complexity.
Many of these packing schemes used in the second pass are unable to process signed data directly. In the LPC and DCT techniques, the data is first remapped adding a binary integer such that positive values are all even numbers and negative values odd numbers. This adds an additional level of processing to the data packing pass.
The present invention contemplates a new and improved data compression technique which overcomes the above-referenced drawbacks and others.